package seqlist;


//车厢类
class DoubleNode {
    //    前驱节点
    DoubleNode perv;
    int val;
    //    后继节点
    DoubleNode next;

    public DoubleNode(int val) {
        this.val = val;
    }
}

/**
 * 基于int的双向链表
 *
 * @author shkstart
 * @create 2022-08-15-22:42
 */


public class DoubleLinkedList {
    private int size;
    //    头节点
    private DoubleNode first;
    //    尾节点
    private DoubleNode last;

    //    添加头节点
    public void addFirst(int val) {
//        一个临时变量保存头节点
        DoubleNode f = first;
        DoubleNode node = new DoubleNode(val);
//        插入头节点
        first = node;
        if (f == null) {
            last = node;
        } else {
            node.next = f;
            f.perv = node;
        }

        size++;
    }

//    添加尾节点

    public void addLast(int val) {
        DoubleNode node = new DoubleNode(val);
        if (last == null) {
            last = node;
            first = node;
        } else {
            last.next = node;
            node.perv = last;
            last = node;
        }
        size++;

    }

    //        任意节点插入
    public void addIndex(int index, int val) {
        if (index == 0) {
            addFirst(val);
        } else if (index == size) {
            addLast(val);
        } else {
//                待插入的节点
            DoubleNode node = node(index);
//                待插入节点的前驱节点
            DoubleNode perv = node.perv;
//                新节点
            DoubleNode newNode = new DoubleNode(val);

//                新节点 与 待插入的节点连接
            newNode.next = node;
            node.perv = newNode;
//                前驱节点与新节点的连接
            perv.next = newNode;
            newNode.perv = perv;

            size++;
        }
    }

    /**
     * 根据index 和 size 的大小关系来判断 指定index 的位置
     *
     * @param index
     * @return
     */
    public DoubleNode node(int index) {
        if (index < size / 2) {
            DoubleNode node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else {
            DoubleNode node = last;
//            从后往前走
            for (int i = size - 1; i > index; i--) {
                node = node.perv;
            }
            return node;
        }
    }

    /**
     * 根据index索引取得节点值
     * @param index
     * @return
     */
    public int get(int index){
        if(rangeCheck(index)){
            DoubleNode node = node(index);
            return node.val;
        }else {
            System.err.println("非法");
            return -1;
        }


    }
    /**
     * 根据index索引修改节点值
     * @param index
     * @return
     */
    public void set(int index,int val){
        if(rangeCheck(index)){
            DoubleNode node = node(index);
            node.val = val;
        }else {
            System.err.println("修改失败");
        }
    }
    public boolean rangeCheck(int index){
        if (index < 0 || index >= size) {
            return  false;
        }
        return true;
    }

    private void nuLinkNode(DoubleNode node){
//        待删除节点的前驱
        DoubleNode prev = node.perv;
//        待删除节点的后继
        DoubleNode next = node.next;

//        分前后两部分进行处理

//        前部分
        if (prev == null) {
//            要删除的是头节点,直接将node的后续节点next当作头节点
            first = next;
        }else{
//            存在前驱节点
            node.perv = null;
            prev.next = next;
        }

//        后半部分
        if (next == null) {
//            要删除的是尾节点,直接将node的前驱perv做尾节点
            last = prev;
        }else{
//            有后续节点
            node.next =null;
            next.perv = prev;
        }

        size--;
    }

//    删除一次
    public void removeValueOnce(int val){
        for(DoubleNode x = first; x!=null;x= x.next){
            if (x.val == val) {
                nuLinkNode(x);
                return ;
            }

        }
    }
//    删除多次
    public void removeValueAll(int val){
        DoubleNode x  = first;
        while (x != null) {
            if (x.val == val) {
//                此时x就是待删除节点
//                但是为了能继续循环,需要暂存x.next;*/
                DoubleNode newx =x.next;
                nuLinkNode(x);
                x=newx;
            }else{
                x=x.next;
            }
        }
    }
    public static void main(String[] args) {
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.addLast(1);
        doubleLinkedList.addLast(2);
        doubleLinkedList.addLast(2);
        doubleLinkedList.addLast(3);
//          1->2->2->3->null
        System.out.println(doubleLinkedList);
        doubleLinkedList.addIndex(1, 10);
        System.out.println(doubleLinkedList);
//        1->10->2->2->3->null
        doubleLinkedList.removeValueAll(2);
        System.out.println(doubleLinkedList);


    }

    @Override
    public String toString() {
        String ret = " ";
        DoubleNode head = first;
        while (head != null) {
            ret += head.val + "->";
            head = head.next;
        }
        ret += "null";
        return ret;
    }
}
